inamerrata

When I last posted about my pygame/trigrid hax0ring, I said:

I’m now at the point where that all works, but there’s no intelligence — peon’s will buy and transport goods without checking first that anyone actually wants them.

Getting past that is proving troublesome, so this is me thinking out loud about it.

The key scenario is having two markets, with an agent who can move goods between them. In the example that should hopefully appear at the right, we’ve got two visible markets (represented by blue circles), and an agent who can carry goods from one to the other (represented by the smaller green circle on the red line). There are three other agents connected to each of the markets, but we’re not concerned about them for the time being. The agent might already own some goods, which could either be stored at one or the other of the markets, or be being carried right now.The agent can move between the two markets (which takes some time), possibly carrying some goods. While at a market, the agent can drop off any goods being carried, or pick up some goods to carry.

As far as trade is concerned, each market maintains a list of offers to sell goods that agents can either add to or accept — in the example pictured, one market has a good offered for $9, and the other has a good offered for $15. Once an offer is accepted, the agent that made the offer is expected to ensure the goods are at the market (by delivering them, eg), and to indicate when this happens, at which point the market transfers ownership to the agent that accepted the offer, and transfers the associated payment in the other direction. The offers are stored in a list in each market, and at the moment, each agent follows the following simple, and stupid, procedure:

while True:
    (src, jobid) = wait_for_a_job()
    (cargo, price) = accept_offer(src, jobid)
    travel_to(src)
    wait_for_job_completion(src, jobid)
    pick_up(cargo)

    dst = other_end(src)
    dst_jobid = make_offer(dst, cargo, price+profit)
    travel_to(dst)
    drop_off(cargo)
    job_is_completed(dst, dst_jobid)

What it should be doing is something more like:

• scanning available offers at one market and making a new offer with some additional profit at the other market
• only accepting an offer when its offer is accepted
• getting payment upfront, so you don’t need to pay the supplier before you’re paid
• dealing with offers and acceptances asynchronously with actually fulfilling them

Somehow the code for that should look something like:

def update_offers(profit, deliver_time):
    for (src, dst) in [(left, right), (right, left)]:
        for (cargo, price, arrive_time) in get_offers(src):
            add_offer(dst, cargo, price + profit, arrive_time + deliver_time)

That risks two instances of unbounded recursion: if get_offers() returns offers made by me, I’ll be making offers to deliver from left to right to left to right to left to… with huge costs and delays. So get_offers() shouldn’t return offers you made. But also, if I offer from my left to my right, someone else offers from right to “up”, and someone else offers from “up” to my left, we have the same problem.

I figure that’s best solved by adding a “contingent” field, to say “this offer is only able to be accepted by you if the offerer is able to accept the contingent offer, otherwise it’s void”. In the event that you have a chain of offers to get from A to B to C to D that allows the markets to accept all the offers simultaneously rather than giving time for some other agent to accept the offer from B and deliver it to E and muck up the whole transaction.

def update_offers(profit, deliver_time):
    delete_my_offers(left)
    delete_my_offers(right)
    for (src, dst) in [(left, right), (right, left)]:
        for (jobid, cargo, price, arrive_time) in get_offers(src):
            contingency = (src, jobid)
            add_offer(dst, cargo, price + profit, arrive_time + deliver_time, contingency)

If you let markets keep track of the “root” of the contingency tree, that also lets you limit the possibility of multi-agent offer loops.

That then needs to be hooked into actually doing the deliveries. When an offer of ours is accepted, two things happen: we’re committed to handing over some goods at one market at time t, and someone else is committed to doing the same at the other market at time t-d. We can thus maintain two lists for each market we interact with: a set of times when some goods are expected to arrive at this market, and a set of times when we’re meant to deliver goods to this market. We can then resolve our obligations by noting that either cargo will arrive at each market before it needs to be delivered, and we can collect our profit without actually doing any work; or else (exactly) one market will require some goods before they arrive, and we’ll have to transport some goods from the other market to satisfy this. Maintaining a schedule of what we should do, and working out a minimum delivery_time for our additional offers should be straightforward at that point.

(For completeness, agents should be able to be penalised for failing to deliver, and potentially rewarded for delivering goods early. Occasionally it’ll work out that the penalties for dropping one commitment will be outweighed by the rewards of delivering on something else — I’m optimistic that just coding that logic should make the overall system much more dynamic while remaining fairly understandable and predictable)

Hmm, I think that covers the next step. Guess we’ll find out when we start coding…